//
// Created by 高森森 on 2022/2/9.
//

#ifndef LEETCODE_SOLUTION27_H
#define LEETCODE_SOLUTION27_H
#include<iostream>
#include<vector>
#include <queue>

using namespace std;

class Solution27 {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>>graph(n);
        vector<int>res;
        for(auto edge:edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        int min=bfs(n,graph,0);
        res.push_back(1);
        for(int i=1;i<n;i++){
            int tmp=bfs(n,graph,i);
            if(tmp<min){
                res.clear();
                res.push_back(i);
                min=tmp;
            }
            else if(tmp==min){
                 res.push_back(i);
            }
        }
        return res;
    }
    //传统的bfs算法超时
    int bfs(int n,vector<vector<int>>&graph,int start){
          queue<int>que;
          que.push(start);
          int count=-1;
          vector<bool>visited(n);
          visited[start]=1;
          while(!que.empty()){
              int size=que.size();
              for(int i=0;i<size;i++){
                  int node=que.front();
                  que.pop();
                  for(auto neigh:graph[node]){
                      if(!visited[neigh]){
                          visited[neigh]=1;
                          que.push(neigh);
                      }
                  }
              }
              count++;
          }
      return count;
    }

     vector<int> findMinHeightTrees2(int n, vector<vector<int>>& edges) {
         vector<vector<int>>graph(n);
         vector<int>ans;
         vector<int>degree(n);
         for(auto edge:edges){
             graph[edge[0]].push_back(edge[1]);
             graph[edge[1]].push_back(edge[0]);
             degree[edge[0]]++;
             degree[edge[1]]++;
         }
         queue<int>que;
         for(int i=0;i<n;i++){
             if(degree[i]==1)
                 que.push(i);
         }
         while(!que.empty()){
             vector<int>res;
             int size=que.size();
             for(int i=0;i<size;i++){
                 int node=que.front();
                 res.push_back(node);
                 que.pop();
                 for(int neigh:graph[node]){
                     degree[neigh]--;
                     if(degree[neigh]==1)
                         que.push(neigh);
                 }
             }
             ans=res;
         }
         return ans;
    }

     };
#endif
